#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: list_sort.py
@time: 2021/12/18 15:55
@desc:
'''
class node:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self) -> str:
        return str(self.val)


class nlist:
    def __init__(self):
        self.head = None
        self.p = self.head

    def add(self, x):
        if isinstance(x, node):
            self.add_node(x)
        else:
            self.add_val(x)

    def add_node(self, node: node):
        if not self.head:
            self.head = node
            self.p = self.head
        else:
            self.p.next = node
            self.p = self.p.next

    def add_val(self, x):
        if not self.head:
            self.head = node(x)
            self.p = self.head
        else:
            self.p.next = node(x)
            self.p = self.p.next

    def get_val(self):
        q = self.head
        nl = []
        while q:
            nl.append(str(q.val))
            q = q.next
        return ','.join(nl)

    def __str__(self) -> str:
        return self.get_val()

    def swap(self, p: node, q: node):
        p.val, q.val = q.val, p.val

    def search_node(self, x):
        q = self.head
        while q:
            if q.val == x: return q
            q = q.next

# 选择排序
def select_sort(head: node):
    if not head: return None
    min = None
    p = head
    while p:
        min = p
        q = p.next
        while q:
            if q.val < min.val:
                min.val, q.val = q.val, min.val
            q = q.next
        p = p.next

# 冒泡排序
def bubble_sort(head: node):
    p = head
    while p:
        q = head
        while q and q.next:
            if q.val>q.next.val:
                q.val, q.next.val = q.next.val, q.val
            q = q.next
        p = p.next

# 归并排序
def merge_sort(head: node):
    def merge(left: node, right: node):
        hd = None
        p = hd
        while left and right:
            if left.val<=right.val:
                if not hd:
                    hd = left; p = hd
                else:
                    p.next = left; left = left.next; p = p.next
            else:
                if not hd:
                    hd = right; p = hd
                else:
                    p.next = right; right = right.next; p = p.next
        while left:
            p.next = left; left = left.next
        while right:
            p.next = right; right=right.next
        return hd

    # 找到中间节点并断开链表
    if not head or not head.next: return
    fp, sp = head, head # 快慢指针
    while fp.next.next:
        fp = fp.next.next
        sp = sp.next
    # 此时的慢指针所在位置即是中点
    mid = sp
    # 第二部分的开头
    mid = mid.next
    # 断开链接
    sp.next = None
    merge(merge_sort(head), merge_sort(mid))










if __name__ == '__main__':
    nl = nlist()
    head = node(25)
    nl.add(head)
    nl.add(10)
    nl.add(23)
    nl.add(12)
    nl.add(1535)
    nl.add(133)
    nl.add(15)
    nl.add(253)
    print(nl)

    # select_sort(head)
    # bubble_sort(head)
    merge_sort(head)
    print(nl)